package debtbundler.mathematics;

import java.util.Vector;

public class Combinations {
	
	/**
	 * Returns a matrix of all M combinations of given objects.
	 * The integer M must be less than or equal to the length of the 
	 * <code>objects</code> vector.
	 * 
	 * The objects in a row in the matrix are sorted in increasing order
	 * by their indices in the <code>objects</code>. 
	 * 
	 * @param objects
	 * 	The objects to pick the M combinations from 
	 * @param M
	 * 	The number of objects in a combination
	 * @return
	 * 	A matrix containing all the M combinations of given objects. Each row contains a combination.
	 */
	public static Object[][] getCombinations(Object[] objects, int M) {
		if (M > objects.length) {
			throw new IllegalArgumentException("The number of objects in a combination must be less than or equal to the number of given objects");
		}
		
		// Initialize
		Vector<int[]> combinationVector = new Vector<int[]>();
		int[] chosenIndices = new int[M];
		
		// Start the recursive combination generation
		chooseNextObject(objects, M, combinationVector, chosenIndices, 0, 0);
				
		// Return the result as specified
		Object[] array = combinationVector.toArray();
		Object[][] result = new Object[array.length][M];
		for (int i=0; i<array.length; ++i) {
			chosenIndices = (int[])array[i];
			for (int j=0; j<M; ++j) {
				result[i][j] = objects[chosenIndices[j]];
			}
		}		
		return result;
	}
	
	/**
	 * Returns a matrix of indices for all M combinations of given objects.
	 * The integer M must be less than or equal to the length of the 
	 * <code>objects</code> vector.
	 * 
	 * The indices in a row in the matrix are sorted in increasing order. 
	 * 
	 * @param objects
	 * 	The objects to pick the M combinations from 
	 * @param M
	 * 	The number of objects in a combination
	 * @return
	 * 	An (N over M) x M matrix containing the indices all M combinations of given objects. Each row contains an index combination.
	 */
	public static int[][] getCombinationIndices(Object[] objects, int M) {
		if (M > objects.length) {
			throw new IllegalArgumentException("The number of objects in a combination must be less than or equal to the number of given objects");
		}
		
		// Initialize
		Vector<int[]> combinationVector = new Vector<int[]>();
		int[] chosenIndices = new int[M];
		
		// Start the recursive combination generation
		chooseNextObject(objects, M, combinationVector, chosenIndices, 0, 0);
		
		// Return the result as specified
		Object[] array = combinationVector.toArray();
		int[][] result = new int[array.length][M];
		for (int i=0; i<array.length; ++i) {
			result[i] = (int[])array[i];
		}		
		return result;
	}
	
	
	private static void chooseNextObject(Object[] objects, int M, Vector<int[]> combinations, int[] chosenIndices, int numberOfElementsChosen, int margin) {
		// Check whether we have selected the required number of objects.
		if (numberOfElementsChosen >= M) {
			// We have. => Store the chosen indices of the combination in the vector and end this recursion branch
			combinations.add(chosenIndices.clone());
			return;
		}
		
		 // Check if there are enough objects to select from. 
		if ( (objects.length - margin) < (M - numberOfElementsChosen) ) {
			// There isn't, so end this recursion branch.
			return;
		}
		
		// There are still new objects to select. 
		for (int i=margin; i < objects.length; ++i) {
			chosenIndices[numberOfElementsChosen] = i; // Store the index of the object selected in the previous step.  
			chooseNextObject(objects, M, combinations, chosenIndices, numberOfElementsChosen+1, i+1); // Try to select new object to right of the object selected in the previous step. 
		}
		
		assert false; // The algorithm should never reach this point.
		
	}
	
}
